package com.wfm.leetcode.editor.cn;

import java.util.HashMap;

public class P剑指Offer39数组中出现次数超过一半的数字{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length==1) return nums[0];
        double n = Math.ceil(1.0*nums.length/2);
        HashMap<Integer,Integer> m = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(m.containsKey(nums[i])){
                int integer = m.get(nums[i]);
                if(integer+1>=n){
                    return nums[i];
                }
                m.put(nums[i],integer+1);
            }else {
                m.put(nums[i],1);
            }
        }
        return -1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指Offer39数组中出现次数超过一半的数字().new Solution();
        int i = solution.majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2});
        System.out.println(i);
    }
}